/******************************************************************************
*  A Teaching GA					  Developed by Hal Stringer & Annie Wu, UCF
*  Version 2, January 18, 2004
*******************************************************************************/

import java.io.FileWriter;
import java.util.ArrayList;
import java.util.Calendar;
import java.util.Date;
import java.util.List;
import java.util.Random;

public class Search {

/*******************************************************************************
*                           INSTANCE VARIABLES                                 *
*******************************************************************************/

/*******************************************************************************
*                           STATIC VARIABLES                                   *
*******************************************************************************/

	public static FitnessFunction problem;

	public static Chromo[] member;
	public static Chromo[] child;

	public static Chromo bestOfGenChromo;
	public static int bestOfGenR;
	public static int bestOfGenG;
	public static Chromo bestOfRunChromo;
	public static int bestOfRunR;
	public static int bestOfRunG;
	public static Chromo bestOverAllChromo;
	public static int bestOverAllR;
	public static int bestOverAllG;

	public static double sumRawFitness;
	public static double sumRawFitness2;	// sum of squares of fitness
	public static double sumSclFitness;
	public static double sumProFitness;
	public static double defaultBest;
	public static double defaultWorst;

	public static double averageRawFitness;
	public static double stdevRawFitness;

	public static int G;
	public static int R;
	public static Random r = new Random();
	private static double randnum;

	private static int memberIndex[];
	private static double memberFitness[];
	private static int TmemberIndex;
	private static double TmemberFitness;

	private static double stdDevStats[][][];  // 0=Avg, 1=Best
	private static double fitnessStats[][];  // 0=Avg, 1=Best
	private static double bestFitnessByRun[];
	private static double avgOptimumFirstFoundGen;
	private static int optimumFoundCount;

/*******************************************************************************
*                              CONSTRUCTORS                                    *
*******************************************************************************/


/*******************************************************************************
*                             MEMBER METHODS                                   *
*******************************************************************************/


/*******************************************************************************
*                             STATIC METHODS                                   *
*******************************************************************************/

	public static void main(String[] args) throws java.io.IOException{

//                Strategy[] strategies = new Strategy[8];
//                String[] names = new String[8];
//
//                names[0] = "always coop and always defect";
//                names[1] = "10 random population members";
//                names[2] = "1 random population member";
//                names[3] = "both tit for tats and 1 random population member";
//                names[4] = "both tit for tats";
//                names[5] = "tit for tat";
//                names[6] = "tit for 2 tats";
//                names[7] = "always defect";
//                
//                //Do IteratedPD results
//                for (int i = 0; i < strategies.length; i++)
//                {
//                    int average = 0;
//                    for (int k = names[i].length(); k < 50; k++)
//                        System.out.printf(" ");
//                    System.out.printf(names[i] + ": ");
//                    for (int j = 0; j < strategies.length; j++)
//                    {
//                        int score;
//                        
//                        strategies[0] = new StrategyEvolved(0,0,24,0);
//                        strategies[1] = new StrategyEvolved(1, 14, 2, 37);
//                        strategies[2] = new StrategyEvolved(1, 2, 25, 120);
//                        strategies[3] = new StrategyEvolved(1, 2, 31, 127);
//                        strategies[4] = new StrategyEvolved(1, 10, 11, 121);
//                        strategies[5] = new StrategyTitForTat();
//                        strategies[6] = new StrategyTitForTwoTats();
//                        strategies[7] = new StrategyAlwaysDefect();
//                        
//                        IteratedPD ipd = new IteratedPD(strategies[i], strategies[j]);
//                        ipd.runSteps(200);
//                        score = ipd.player1Score();
//                        System.out.printf(ipd.player1Score() + " ");
//                        //System.out.println(score);
//                        average += score;
//                    }
//                    System.out.printf("  Avg: " + average/strategies.length);
//                    System.out.println();
//                }
//                System.exit(1);
            
		Calendar dateAndTime = Calendar.getInstance(); 
		Date startTime = dateAndTime.getTime();

	//  Read Parameter File
		System.out.println("\nParameter File Name is: " + args[0] + "\n");
		new Parameters(args[0]);
		
	//  Write Parameters To Summary Output File
		String summaryFileName = Parameters.expID + "_summary.txt";
		FileWriter summaryOutput = new FileWriter(summaryFileName);
		Parameters.outputParameters(summaryOutput);

	//	Set up Fitness Statistics matrix
		fitnessStats = new double[2][Parameters.generations];
		for (int i=0; i<Parameters.generations; i++){
			fitnessStats[0][i] = 0;
			fitnessStats[1][i] = 0;
		}
		
		stdDevStats = new double[2][Parameters.numRuns+1][Parameters.generations];
		for (int i=1; i<=Parameters.numRuns; i++){
			for (int j=0; j<Parameters.generations; j++)
			{
				stdDevStats[0][i][j] = 0;
				stdDevStats[1][i][j] = 0;
			}
		}
		
		bestFitnessByRun = new double[Parameters.numRuns+1];
		for (int i=1; i<=Parameters.numRuns; i++)
		{
			bestFitnessByRun[i] = 0;
		}
		
		avgOptimumFirstFoundGen = 0;
		optimumFoundCount = 0;
		
	//	Problem Specific Setup - For new new fitness function problems, create
	//	the appropriate class file (extending FitnessFunction.java) and add
	//	an else_if block below to instantiate the problem.
 
		if (Parameters.problemType.equals("NM")){
				problem = new NumberMatch();
		}
		else if (Parameters.problemType.equals("OM")){
				problem = new OneMax();
		}
                else if (Parameters.problemType.equals("IPD"))
                {
                                problem = new IPD();
                }
		else System.out.println("Invalid Problem Type");

		System.out.println(problem.name);

	//	Initialize RNG, array sizes and other objects
		r.setSeed(Parameters.seed);
		memberIndex = new int[Parameters.popSize];
		memberFitness = new double[Parameters.popSize];
		member = new Chromo[Parameters.popSize];
		child = new Chromo[Parameters.popSize];
		bestOfGenChromo = new Chromo();
		bestOfRunChromo = new Chromo();
		bestOverAllChromo = new Chromo();

		if (Parameters.minORmax.equals("max")){
			defaultBest = 0;
			defaultWorst = 999999999999999999999.0;
		}
		else{
			defaultBest = 999999999999999999999.0;
			defaultWorst = 0;
		}

		bestOverAllChromo.rawFitness = defaultBest;

		//  Start program for multiple runs
		for (R = 1; R <= Parameters.numRuns; R++){
			
			double[] bestOfGeneration = new double[Parameters.generations];
			int optimumFoundAt = -1;
			bestOfRunChromo.rawFitness = defaultBest;
			System.out.println();

			//	Initialize First Generation
			for (int i=0; i<Parameters.popSize; i++){
				member[i] = new Chromo();
				child[i] = new Chromo();
			}

			//	Begin Each Run
			for (G=0; G<Parameters.generations; G++){

				sumProFitness = 0;
				sumSclFitness = 0;
				sumRawFitness = 0;
				sumRawFitness2 = 0;
				bestOfGenChromo.rawFitness = defaultBest;

				//	Test Fitness of Each Member
				for (int i=0; i<Parameters.popSize; i++){

					member[i].rawFitness = 0;
					member[i].sclFitness = 0;
					member[i].proFitness = 0;

					problem.doRawFitness(member[i]);

					sumRawFitness = sumRawFitness + member[i].rawFitness;
					sumRawFitness2 = sumRawFitness2 +
						member[i].rawFitness * member[i].rawFitness;

					if (Parameters.minORmax.equals("max")){
						if (member[i].rawFitness > bestOfGenChromo.rawFitness){
							Chromo.copyB2A(bestOfGenChromo, member[i]);
							bestOfGenR = R;
							bestOfGenG = G;
						}
						if (member[i].rawFitness > bestOfRunChromo.rawFitness){
							Chromo.copyB2A(bestOfRunChromo, member[i]);
							bestOfRunR = R;
							bestOfRunG = G;
						}
						if (member[i].rawFitness > bestOverAllChromo.rawFitness){
							Chromo.copyB2A(bestOverAllChromo, member[i]);
							bestOverAllR = R;
							bestOverAllG = G;
						}
					}
					else {
						if (member[i].rawFitness < bestOfGenChromo.rawFitness){
							Chromo.copyB2A(bestOfGenChromo, member[i]);
							bestOfGenR = R;
							bestOfGenG = G;
						}
						if (member[i].rawFitness < bestOfRunChromo.rawFitness){
							Chromo.copyB2A(bestOfRunChromo, member[i]);
							bestOfRunR = R;
							bestOfRunG = G;
						}
						if (member[i].rawFitness < bestOverAllChromo.rawFitness){
							Chromo.copyB2A(bestOverAllChromo, member[i]);
							bestOverAllR = R;
							bestOverAllG = G;
						}
					}
					
					//Test for optimality
					if (problem instanceof IPD)
					{
						IPD ipd = (IPD)problem;
						
						//TODO Compute optimum IPD?
						/*
						if (optimumFoundAt == -1 && member[i].rawFitness == packingProblem.maxPossibleArea)
						{
							optimumFoundAt = G;
						}
						*/
					}
				}

				// Accumulate fitness statistics
				fitnessStats[0][G] += sumRawFitness / Parameters.popSize;
				fitnessStats[1][G] += bestOfGenChromo.rawFitness;
				stdDevStats[0][R][G] = sumRawFitness / Parameters.popSize;
				stdDevStats[1][R][G] = bestOfGenChromo.rawFitness;
				
				bestOfGeneration[G] = bestOfGenChromo.rawFitness;
				
				averageRawFitness = sumRawFitness / Parameters.popSize;
				stdevRawFitness = Math.sqrt(
							Math.abs(sumRawFitness2 - 
							sumRawFitness*sumRawFitness/Parameters.popSize)
							/
							(Parameters.popSize-1)
							);

				// Output generation statistics to screen
				System.out.println(R + "," + G +  "," + bestOfGenChromo.rawFitness + "," + averageRawFitness + "," + stdevRawFitness);

				// Output generation statistics to summary file
				summaryOutput.write("R,");
				Hwrite.right(R, 3, summaryOutput);
				summaryOutput.write("G,");
				Hwrite.right(G, 3, summaryOutput);
				Hwrite.right(bestOfGenChromo.rawFitness, 7, summaryOutput);
				Hwrite.right(averageRawFitness, 11, 3, summaryOutput);
				Hwrite.right(stdevRawFitness, 11, 3, summaryOutput);
				summaryOutput.write("\n");


		// *********************************************************************
		// **************** SCALE FITNESS OF EACH MEMBER AND SUM ***************
		// *********************************************************************

				switch(Parameters.scaleType){

				case 0:     // No change to raw fitness
					for (int i=0; i<Parameters.popSize; i++){
						member[i].sclFitness = member[i].rawFitness + .000001;
						sumSclFitness += member[i].sclFitness;
					}
					break;

				case 1:     // Fitness not scaled.  Only inverted.
					for (int i=0; i<Parameters.popSize; i++){
						member[i].sclFitness = 1/(member[i].rawFitness + .000001);
						sumSclFitness += member[i].sclFitness;
					}
					break;

				case 2:     // Fitness scaled by Rank (Maximizing fitness)

					//  Copy genetic data to temp array
					for (int i=0; i<Parameters.popSize; i++){
						memberIndex[i] = i;
						memberFitness[i] = member[i].rawFitness;
					}
					//  Bubble Sort the array by floating point number
					for (int i=Parameters.popSize-1; i>0; i--){
						for (int j=0; j<i; j++){
							if (memberFitness[j] > memberFitness[j+1]){
								TmemberIndex = memberIndex[j];
								TmemberFitness = memberFitness[j];
								memberIndex[j] = memberIndex[j+1];
								memberFitness[j] = memberFitness[j+1];
								memberIndex[j+1] = TmemberIndex;
								memberFitness[j+1] = TmemberFitness;
							}
						}
					}
					//  Copy ordered array to scale fitness fields
					for (int i=0; i<Parameters.popSize; i++){
						member[memberIndex[i]].sclFitness = i;
						sumSclFitness += member[memberIndex[i]].sclFitness;
					}

					break;

				case 3:     // Fitness scaled by Rank (minimizing fitness)

					//  Copy genetic data to temp array
					for (int i=0; i<Parameters.popSize; i++){
						memberIndex[i] = i;
						memberFitness[i] = member[i].rawFitness;
					}
					//  Bubble Sort the array by floating point number
					for (int i=1; i<Parameters.popSize; i++){
						for (int j=(Parameters.popSize - 1); j>=i; j--){
							if (memberFitness[j-i] < memberFitness[j]){
								TmemberIndex = memberIndex[j-1];
								TmemberFitness = memberFitness[j-1];
								memberIndex[j-1] = memberIndex[j];
								memberFitness[j-1] = memberFitness[j];
								memberIndex[j] = TmemberIndex;
								memberFitness[j] = TmemberFitness;
							}
						}
					}
					//  Copy array order to scale fitness fields
					for (int i=0; i<Parameters.popSize; i++){
						member[memberIndex[i]].sclFitness = i;
						sumSclFitness += member[memberIndex[i]].sclFitness;
					}

					break;

				default:
					System.out.println("ERROR - No scaling method selected");
				}


		// *********************************************************************
		// ****** PROPORTIONALIZE SCALED FITNESS FOR EACH MEMBER AND SUM *******
		// *********************************************************************

				for (int i=0; i<Parameters.popSize; i++){
					member[i].proFitness = member[i].sclFitness/sumSclFitness;
					sumProFitness = sumProFitness + member[i].proFitness;
				}

		// *********************************************************************
		// ************ CROSSOVER AND CREATE NEXT GENERATION *******************
		// *********************************************************************

				int parent1 = -1;
				int parent2 = -1;

				//  Assumes always two offspring per mating
				for (int i=0; i<Parameters.popSize; i=i+2){

					//	Select Two Parents
					parent1 = Chromo.selectParent();
					parent2 = parent1;
					while (parent2 == parent1){
						parent2 = Chromo.selectParent();
					}

					//	Crossover Two Parents to Create Two Children
					randnum = r.nextDouble();
					if (randnum < Parameters.xoverRate){
//                                                System.out.println("Parents");
//                                                StrategyEvolved.printParameterSettings(member[parent1].chromo, member[parent2].chromo);
						Chromo.mateParents(parent1, parent2, member[parent1], member[parent2], child[i], child[i+1]);
//                                                System.out.println("Children after Crossover");
//                                                StrategyEvolved.printParameterSettings(child[i].chromo, child[i+1].chromo);
//                                                System.out.println("Children after Mutation");
//                                                child[i].doMutation();
//                                                child[i+1].doMutation();
//                                                StrategyEvolved.printParameterSettings(child[i].chromo, child[i+1].chromo);
//                                                System.out.println();
					}
					else {
						Chromo.mateParents(parent1, member[parent1], child[i]);
						Chromo.mateParents(parent2, member[parent2], child[i+1]);
					}
				} // End Crossover

				//	Mutate Children
				for (int i=0; i<Parameters.popSize; i++){
					child[i].doMutation();
				}

				//	Swap Children with Last Generation
				for (int i=0; i<Parameters.popSize; i++){
					Chromo.copyB2A(member[i], child[i]);
				}

			} //  Repeat the above loop for each generation

			//Hwrite.left(bestOfRunR, 4, summaryOutput);
			//Hwrite.right(bestOfRunG, 4, summaryOutput);
			//problem.doPrintGenes(bestOfRunChromo, summaryOutput);
			summaryOutput.write("BestOfRun"
					+ " R=" + bestOfRunR
					+ " G=" + bestOfRunG
					+ " Val=" + bestOfRunChromo.rawFitness + "\n");
			summaryOutput.write("OptimumFirstFoundAt" 
					+ " R=" + bestOfRunR
					+ " G=" + optimumFoundAt + "\n");
			
			System.out.println(R + "," + "B" + ","+ bestOfRunChromo.rawFitness);
			
			summaryOutput.write("\n");
			
			bestFitnessByRun[R] = bestOfRunChromo.rawFitness;
			
			if (optimumFoundAt != -1)
			{
				avgOptimumFirstFoundGen += optimumFoundAt;
				optimumFoundCount++;
			}
		} //End of a Run

		//Hwrite.left("B", 8, summaryOutput);
		//problem.doPrintGenes(bestOverAllChromo, summaryOutput);	

		//problem.doPrintGenes(bestOverAllChromo, summaryOutput);

		//	Output Fitness Statistics matrix
		summaryOutput.write("Gen            AvgFit              BestFit              AvgFitStdDev              BestFitStdDev\n");
		for (int i=0; i<Parameters.generations; i++)
		{
			double avgFit = fitnessStats[0][i]/Parameters.numRuns;
			double bestFit = fitnessStats[1][i]/Parameters.numRuns;
			double avgFitStdDev = 0.0;
			double bestFitStdDev = 0.0;
			
			for (int run=1; run<=Parameters.numRuns; run++)
			{
				avgFitStdDev += Math.pow(stdDevStats[0][run][i] - avgFit, 2);
			}
			avgFitStdDev = Math.sqrt(avgFitStdDev / Parameters.numRuns);
			
			for (int run=1; run<=Parameters.numRuns; run++)
			{
				bestFitStdDev += Math.pow(stdDevStats[1][run][i] - bestFit, 2);
			}
			bestFitStdDev = Math.sqrt(bestFitStdDev / Parameters.numRuns);
			
			Hwrite.left(i, 15, summaryOutput);
			Hwrite.left(avgFit, 20, 2, summaryOutput);
			Hwrite.left(bestFit, 20, 2, summaryOutput);
			Hwrite.left(avgFitStdDev, 20, 2, summaryOutput);
			Hwrite.left(bestFitStdDev, 20, 2, summaryOutput);
			summaryOutput.write("\n");
		}

		double avgBestFitnessByRun = 0.0;
		double avgBestFitnessByRunStdDev = 0.0;
		
		for (int run=1; run<=Parameters.numRuns; run++)
		{
			avgBestFitnessByRun += bestFitnessByRun[run] / Parameters.numRuns;
		}
		
		for (int run=1; run<=Parameters.numRuns; run++)
		{
			avgBestFitnessByRunStdDev += Math.pow(bestFitnessByRun[run] - avgBestFitnessByRun, 2);
		}
		avgBestFitnessByRunStdDev = Math.sqrt(avgBestFitnessByRunStdDev / Parameters.numRuns);
		
		summaryOutput.write("Average Best Fitness over all runs: " + avgBestFitnessByRun + " with Std Dev " + avgBestFitnessByRunStdDev + "\n");
		
		double avgOptimumOut = -1;
		
		if (optimumFoundCount > 0)
		{
			avgOptimumFirstFoundGen /= optimumFoundCount;
			avgOptimumOut = avgOptimumFirstFoundGen;
		}
		
		summaryOutput.write("Average Optimum First Found Gen:" + avgOptimumOut);
		summaryOutput.write("\n\n");
		
		//Tack on best values found for other strats
		if (problem instanceof IPD)
		{
			IPD ipd = (IPD)problem;
			
			StrategyEvolved ourBestStrat = IPD.chromoValueToStrategy(bestOverAllChromo.chromo);
			
			summaryOutput.write("Best of our Strategy: " + bestOverAllChromo.rawFitness + "\n");
			summaryOutput.write(ourBestStrat.getParameterSettings() + "\n");
			
			
			//Add to map for sorting purposes
			ipd.staticStratToBestMap.put(ourBestStrat, bestOverAllChromo.rawFitness);
			
			ipd.staticStratToBestMap = IPD.sortByValue(ipd.staticStratToBestMap);
			summaryOutput.write("BestOfAll Fitness for Static Strategies\n");
			for (Strategy strat : ipd.staticStratToBestMap.keySet())
			{
				double bestFitnessVal = ipd.staticStratToBestMap.get(strat);
				
				//summaryOutput.write(strat.name + ":" + bestFitnessVal + "\n");
				Hwrite.left(strat.name, 25, summaryOutput);
				Hwrite.left(bestFitnessVal, 25, 2, summaryOutput);
				summaryOutput.write("\n");
			}
		}
		else
		{
			summaryOutput.write("BestOfAll"
					+ " Fitness=" + bestOverAllChromo.rawFitness + "\n");
		}
		
		summaryOutput.close();

		System.out.println();
		System.out.println("Start:  " + startTime);
		dateAndTime = Calendar.getInstance(); 
		Date endTime = dateAndTime.getTime();
		System.out.println("End  :  " + endTime);

	} // End of Main Class
}   // End of Search.Java ******************************************************

